Common key block cipher is known as a technology that conceals communication data or accumulated data. A block cipher encrypts data to be encrypted by dividing the data into a predetermined unit called block length. DES (Data Encryption Standard), proposed in the 1970s, is a typical block cipher. DES employs a Feistel structure as the structure of its data randomizing unit.
FIG. 4 is a drawing showing an encryption process using an r-round Feistel structure that generates an m-bit encrypted text C from an m-bit plain text P. One round of processing in the Feistel structure includes an F function processing unit 10 and a transposition processing unit 11. The F function processing unit 10 receives two pieces of m/2-bit data and key data Ki, outputs one of the pieces of data as it is, performs an exclusive OR (“+” symbols in circle in FIG. 4; referred to as “XOR” hereinafter) between data obtained by performing conversion of an F function on one of the pieces of data using the key data Ki and the other piece of the data, and outputs the result. The transposition processing unit 11 shuffles the two pieces of data received and outputs them. Only in the final r-th round, the transposition processing unit 11 does not perform its processing and only the processing by the F function processing unit 10 is performed.
FIG. 5 is a drawing showing a decryption process corresponding to the encryption process in FIG. 4. The decryption process in FIG. 5 includes the same F function processing unit 10 and transposition processing unit 11 as the encryption process in FIG. 4. Decryption of the Feistel structure can be done by performing the encryption process in the reverse order (going back from the bottom in FIG. 4).
Both the F function processing unit 10 and the transposition processing unit 11 have a vertically symmetrical structure. Further, the encryption process in FIG. 4 and the decryption process in FIG. 5 have a vertically symmetrical structure as a whole. Therefore, just by reversing the order of use of the used key data in each round, both encryption and decryption become possible. As described, according to DES, the encryption process and the decryption process can share the round processing, and the implementation scale can be reduced, compared with the SPN (Substitution Permutation Network) structure, represented by AES (Advanced Encryption Standard).
Further, generalized Feistel structure, in which the number of blocks of the Feistel structure is expanded to two or more, is known (Non Patent Literature 1). In Non Patent Literature 1, the generalized Feistel structure is referred to as Feistel-Type Transformation (FTT). Non Patent Literature 1 proposes three kinds of structures from Type-1 to Type-3, however, only Type-2 will be described here. Unless stated otherwise, the “generalized Feistel structure” refers to Type-2 generalized Feistel structure hereinafter.
FIG. 6 is a drawing showing an example of a generalized Feistel structure. The drawing shows an encryption process having a generalized Feistel structure dividing data into eight blocks. One round of processing in the generalized Feistel structure includes an F function processing unit 30 and a transposition processing unit 31. The F function processing unit 30 comprises four F function processing units 10 in parallel. In a case of k-partitions, the F function processing unit 30 is generally constituted by k/2 F function processing units 10 in parallel. The F function processing unit 30 performs conversion of an F function on four sets of data, in which eight pieces of m/8-bit data are paired, and outputs eight pieces of data. The transposition processing unit 31 cyclically shifts the eight pieces of data to the left. Only in the final r-th round, the transposition processing unit 31 does not perform its processing and only the processing by the F function processing unit 30 is performed.
Further, Japanese Patent Application 2009-246306 proposes a generalized Feistel structure in which the transposition processing unit 31 performs a transposition process other than cyclic shift.
FIG. 7 is a drawing showing a decryption process corresponding to the encryption process in FIG. 6. An F function processing unit 30 in the decryption process and the F function processing unit 30 in the encryption process are identical. However, a transposition processing unit 40 is obtained by turning the transposition processing unit 31 upside down; therefore, the transposition processing unit 40 and the transposition processing unit 31 in the encryption process are different.
As described, in the Feistel structure, the encryption process and the decryption process can share the F function processing unit 10 and the transposition processing unit 11. On the other hand, the encryption process and the decryption process cannot share the same transposition processing unit in the generalized Feistel structure.
As an example, Patent Literature (PTL) 1 describes a structure in which an encryption function and a decryption function are shared in an extended Feistel type common key block cipher.
PTL 1:
    Japanese Patent Kokai Publication No. JP2008-058826ANPL 1:    Y. Zheng, T. Matsumoto, H. Imai, “On the Construction of Block Ciphers Provably Secure and Not Relying on Any Unproved Hypotheses,” CRYPTO 1989, LNCS vol. 435, pp. 461-480, Springer-Verlag, 1990.